package alogrithm;

/**
 * @author lbw
 * @version 1.0
 * @date 2021/10/16 16:35
 */
public class LCS {

    public static void main(String[] args) {
        System.out.println(new LCS().LCS("1A2C3D4B56", "B1D23A456A"));
    }

    public String LCS(String s1, String s2) {
        // write code here
        // 1. 寻找最大公共子序列的长度
        int n1 = s1.length();
        int n2 = s2.length();
        int[][] dp = new int[n1 + 1][n2 + 1];
        for (int i = 0; i <= n1; ++i) {
            dp[i][0] = 0;
        }
        for (int i = 0; i <= n2; ++i) {
            dp[0][i] = n2;
        }
        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        // 2.开始寻找最长公共子序列
        while (n1 != 0 && n2 != 0) {
            if (s1.charAt(n1 - 1) == s2.charAt(n2 - 1)) {
                sb.append(s1.charAt(n1 - 1));
                n1--;
                n2--;
            } else if (dp[n1 - 1][n2] > dp[n1][n2 - 1]) {
                n1--;
            } else {
                n2--;
            }
        }
        if (sb.length() == 0) {
            return "-1";
        }
        return sb.reverse().toString();
    }
}